#include "Utility.h"
#include <vector>
using std::vector;
class LinearTimeChoose
{
public :
	template <class Type>
	Type randomizeSelect(vector<Type> &data, int start, int end, int search_target)
	{
		if(start == end)
			return data[start];
		else
		{
			int divide_position = randomizedPartition(data,start,end);
			int first_array_num = divide_position - start +1;
			if(search_target <=  first_array_num)
			{
				return randomizeSelect(data,start,divide_position,search_target);
			}
			else
			{
				return randomizeSelect(data,divide_position+1,end,search_target-first_array_num);
			}
		}
	}
private:
	template <class Type>
	int randomizedPartition(vector<Type> &data,int start,int end)
	{
		int i = Utility::random(start,end);
		Utility::swap(data[start],data[i]);
		return partition(data,start,end);
	}
	template <class Type>
	int partition(vector<Type> &data,int start,int end)
	{
		int i = start;
		int j = end+1;
		Type x = data[start];
		while(true)
		{
			while(data[--j] >= x && j>i);
			data[i] = data[j];
			while(data[++i] <= x && i < j);
			data[j] = data[i];
			if(i>=j)
				break;
		}

		data[j] = x;
		return j;
	}
};
